// 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字：
// '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。
// 每个拨轮可以自由旋转：例如把 '9' 变为  '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
// 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
// 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
// 字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。

function openLock(deadends: string[], target: string): number {
  // 向上拨动
  function tickUp(s: any, index: number) {
    s = s.split("");
    s[index] = s[index] === "9" ? "0" : (parseInt(s[index]) + 1).toString();
    return s.join("");
  }
  // 向下拨动
  function tickDown(s: any, index: number) {
    s = s.split("");
    s[index] = s[index] === "0" ? "9" : (parseInt(s[index]) - 1).toString();
    return s.join("");
  }
  const queue: string[] = []; // 队列
  const hashSet = new Set<string>(deadends); // 哈希集合
  const visited = new Set<string>(); // 已经出现过的元素
  queue.push("0000"); // 起始数字
  let count: number = 0; // 计算轮次
  while (queue.length > 0) {
    let currCount = queue.length; // 当前轮次长度
    for (let i = 0; i < currCount; i++) {
      let curr = queue.shift() as string; // 出队当前元素
      if (curr === target) return count; // 如果命中则直接返回计数轮次
      if (hashSet.has(curr)) continue; // 如果在死亡数字列表中，下一轮循环
      for (let i = 0; i < 4; i++) {
        // 尝试四种可能
        let up = tickUp(curr, i);
        if (!visited.has(up)) {
          // 如果没有出现过
          visited.add(up);
          queue.push(up);
        }
        let down = tickDown(curr, i);
        if (!visited.has(down)) {
          visited.add(down);
          queue.push(down);
        }
      }
    }
    count++;
  }
  return -1;
}


// 这道题目是一道非常经典的广度优先搜索算法的例题.
